package com.ting.test.algorithms.大厂刷题班;

/***
 * 求一个字符串最长无重复子串的长度
 * 思路
 * 利用动态规划的思想
 *
 * 当我的子串以i位置结尾时，从0，到i的最长无重复子串的长度是多少
 * 遍历每个位置，求最大值
 *
 */
public class 求一个字符串最长无重复子串的长度 {

    public static void main(String[] args) {
        String s = "afadfadsfaerweafasdfadsfasdfa";
        int length = process(s);
    }

    private static int process(String s) {
        if (null == s || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int[] map = new int[255];//定义一个ascii码范围的数组，存储可能出现的元素最近一次出现的位置
        int ans = 1;//i位置的最长无重复子串，0是他本身 长度为1
        int pre = 1;//表示上一个子串的长度

        for (int i = 1; i < str.length; i++) {
            // 这里需要注意
            // 要找到最长的无重复子串，首先要找到以当前位置元素结尾的最长的重复子串是什么
            //那么有两种可能，
            // 第一种 ,当前位置的元素到上一个出现该元素的位置之间的长度是以该位置元素结尾的一个重复子串
            //第二种，要看上一个i-1位置的元素的最长无重复子串的长度是多少
            //要取两种的最小值
            ans = Math.min(pre + 1, i - map[str[i - 1]]);//i-map[str[i]]表示上一个i位置的元素出现的位置
            map[str[i]] = i;//重置i位置的元素最近一次出现的位置
            pre = ans;
        }
        return ans;
    }
}
